package com.dbh.alg.algorithm.hot100.普通数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，
 * 该数组需恰好覆盖输入中的所有区间 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2：
 *
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 *
 * 提示：
 *
 * 1 <= intervals.length <= 104
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 104
 */
public class Leetcode56_合并区间 {

    public int[][] merge(int[][] intervals) {
        // 如果区间为空或只有一个区间，直接返回
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

        // 按区间的起始点进行排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        // 使用 List 来动态存储合并后的区间
        List<int[]> merged = new ArrayList<>();
        // 将第一个区间加入结果列表
        merged.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] current = intervals[i];
            int[] last = merged.get(merged.size() - 1);

            // 如果当前区间的起始点 <= 上一个区间的结束点，说明有重叠
            if (current[0] <= last[1]) {
                // 合并区间，结束点取两者的最大值
                last[1] = Math.max(last[1], current[1]);
            } else {
                // 否则，将当前区间加入结果列表
                merged.add(current);
            }
        }

        // 将 List 转换为数组返回
        return merged.toArray(new int[merged.size()][]);
    }

}
